package LowOrderSortingAlgorithm;

public class EvenTimesOddTimes {

    /*
        相同的数异或后等于0
        不相同的数异或后等于1
        N ^ N = 0
        N ^ 0 = N
     */

    /*
        一个数组中
        有一个数出现了奇数次
        其余数都出现了偶数次
        找出出现了奇数次的那个数
     */
    public static void printOddTimesNum1(int[] arr) {
        int eor = 0;
        for (int cur : arr) {
            eor ^= cur;
        }
        System.out.println(eor);
    }

    /*
        一个数组中
        有两个数出现了奇数次
        其余数都出现了偶数次
        找出出现了奇数次的那两个数
     */
    public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int curNum : arr) {
            eor ^= curNum;
        }
        // eor = a ^ b
        // eor != 0
        // eor必然有一个位置上是1
        int rightOne = eor & (~eor +1);// 提取出最右边的1

        int onlyOne = 0;// eor'
        for (int cur : arr) {
            if ((cur & rightOne) == 0) {
                onlyOne ^= cur;
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }


    public static void main(String[] args) {
        int[] arr = new int[]{1,5,4,8,3,2,7,3,1,6,2,3,4,5,6,7,8};
        printOddTimesNum1(arr);

        int[] arr2 = new int[]{1,5,4,8,3,2,7,3,1,6,2,3,4,5,6,7,8,1};
        printOddTimesNum2(arr2);
    }
}
